package com.banmoon.datastructure.BalanceBinaryTree;

import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;
import java.util.Objects;

@Data
public class BalanceBinaryTree {

    private Node root;

    /**
     * 添加节点
     * @param value
     */
    public void add(int value) {
        if (Objects.isNull(root))
            this.root = new Node(value);
        else
            root.add(new Node(value), this, null);
    }

    /**
     * 生成二叉查找树
     * @param values
     * @return
     */
    public static BalanceBinaryTree generate(int[] values) {
        BalanceBinaryTree binarySearchTree = new BalanceBinaryTree();
        Arrays.stream(values).forEach(binarySearchTree::add);
        return binarySearchTree;
    }

    /**
     * 中序遍历
     */
    public void show() {
        if (Objects.nonNull(this.root))
            this.root.show();
    }

    public boolean isBalance() {
        if (Objects.isNull(this.root))
            return true;
        return Math.abs(this.root.heightDifference()) <= 1;
    }

}

@Data
@NoArgsConstructor
class Node {
    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node(int value) {
        this.value = value;
    }

    public void add(Node node, BalanceBinaryTree tree, Node parent) {
        if(Objects.isNull(node))
            return;
        if (node.getValue() < this.value) {
            if (Objects.nonNull(this.leftNode))
                this.leftNode.add(node, tree, this);
            else
                this.leftNode = node;
        } else {
            if (Objects.nonNull(this.rightNode))
                this.rightNode.add(node, tree, this);
            else
                this.rightNode = node;
        }
        // 检查是否平衡二叉树，此处说明左子树的高度比右子树要高，导致的不平衡，需要进行右旋转
        if (this.heightDifference() > 1) {
            // 如果左节点的左子树高度比其右子树的高度要小，就需要对其进行一次左旋转
            if (this.leftNode.leftHeight() < this.leftNode.rightHeight())
                this.leftNode.leftRotate(tree, this);
            this.rightRotate(tree, parent);
        }
        // 此处说明右子树的高度比左子树要高，需要进行左旋转
        else if (this.heightDifference() < -1) {
            // 如果右节点的左子树高度比其右子树的高度要大，就需要对其进行一次右旋转。避免整体左旋转后，高度不平衡
            if (this.rightNode.leftHeight() > this.rightNode.rightHeight())
                this.rightNode.rightRotate(tree, this);
            this.leftRotate(tree, parent);
        }
    }

    /**
     * 对当前节点进行右旋转
     */
    private void rightRotate(BalanceBinaryTree tree, Node parent) {
        // 取得当前节点的左节点
        Node tempLeftNode = this.leftNode;
        // 将当前节点的左节点置空
        this.leftNode = null;
        // 取得原先左节点的右节点，让其作为新的节点插入至当前节点的子树中
        this.add(tempLeftNode.rightNode, tree, parent);
        // 将原先左节点的右节点设置为当前节点
        tempLeftNode.rightNode = this;
        // 判断当前节点是否是根节点，将原先的左节点设置为根节点
        if (tree.getRoot() == this)
            tree.setRoot(tempLeftNode);
        // 父节点的右节点指向原先的左节点
        else
            parent.rightNode = tempLeftNode;
    }

    /**
     * 对当前节点进行左旋转
     */
    private void leftRotate(BalanceBinaryTree tree, Node parent) {
        // 取得当前节点的右节点
        Node tempRightNode = this.rightNode;
        // 将当前节点的右节点置空
        this.rightNode = null;
        // 取得原先右节点的左节点，让其作为新的节点插入至当前节点的子树中
        this.add(tempRightNode.leftNode, tree, parent);
        // 将原先右节点的左节点设置为当前节点
        tempRightNode.leftNode = this;
        // 判断当前节点是否是根节点，将原先的右节点设置为根节点
        if (tree.getRoot() == this)
            tree.setRoot(tempRightNode);
        // 父节点的左节点指向原先的右节点
        else
            parent.leftNode = tempRightNode;
    }

    /**
     * 高度差
     * @return
     */
    public int heightDifference() {
        return leftHeight() - rightHeight();
    }

    /**
     * 当前节点的高度
     * @return
     */
    public int height() {
        return Math.max(leftHeight(), rightHeight()) + 1;
    }

    /**
     * 左子树的高度
     * @return
     */
    public int leftHeight() {
        return Objects.isNull(this.leftNode)? 0 : this.leftNode.height();
    }

    /**
     * 左子树的高度
     * @return
     */
    public int rightHeight() {
        return Objects.isNull(this.rightNode)? 0 : this.rightNode.height();
    }

    public void show() {
        if (Objects.nonNull(this.leftNode))
            this.leftNode.show();
        System.out.print(this.value + ", ");
        if (Objects.nonNull(this.rightNode))
            this.rightNode.show();
    }
}